package leetcode;

/*
606. 根据二叉树创建字符串
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:
输入: 二叉树: [1,2,3,4]
       1
     /   \
    2     3
   /
  4
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。
示例 2:
输入: 二叉树: [1,2,3,null,4]
       1
     /   \
    2     3
     \
      4
输出: "1(2()(4))(3)"
解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
*/

public class problems_606 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(4);
        A1.left = A2;
        A1.right = A3;
        A2.right = A4;
        System.out.println(new Solution().tree2str(A1));
    }
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    static class Solution {
        StringBuffer ret = new StringBuffer();
        int max = 0;
        public String tree2str(TreeNode t) {
            dfs(t, 0);
            return ret.toString();
        }
        private void dfs(TreeNode node, int floor){
            if(null == node) return;
            max = Math.max(max, floor);
            if(floor != 0) ret.append("(");
            ret.append(node.val);
            if(null == node.left && null != node.right) ret.append("()");
            dfs(node.left, floor+1);
            dfs(node.right, floor+1);
            if(floor != 0) ret.append(")");
        }
    }
}